// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-13 18:46
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

public class WaysToStep {
    /**
     * 爬楼梯 -> 1 + 2 +3
     *
     * @param n 上n级台阶
     * @return 总共有多少种方法
     */
    public int waysToStep(int n) {
        // 动态规划
        if (n == 0) {
            return 1;
        } else if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        }
        int first = 1, second = 2, third = 4;
        for (int i = 4; i <= n; i++) {
            if (i == 30) {
                int k = 0;
            }
            int tmp = third;
            third = (((first + second) % 1_000_000_007) + third) % 1_000_000_007;
            first = second % 1_000_000_007;
            second = tmp % 1_000_000_007;
        }
        return third;
    }

    @Test
    public void shout() {
        System.out.println(waysToStep(61));
    }
}
